/**
 * @author 汤奇
 * @version V1.0
 * @Project BookPro
 * @Package PACKAGE_NAME
 * @Description: 41个人, 围成一个圈, 约瑟夫环自杀顺序, 希望计算出自杀顺序, 以便提前选位
 * @Date 2022/7/26 19:18
 */
public class Test06 {
    public static void main(String[] args) {
        Node<Integer> top = new Node<>();
        Node<Integer> p = top;

        p.value = 1;
        p.next = new Node<>();

        p.next.value = 2;
        p.next.prev = p;

        Node<Integer> temp = new Node<>();
        temp.value = 100;

        temp.next = p.next;
        temp.prev = p;
        p.next = temp;
        p.next.next.prev = temp;

        System.out.println(top.value);
        System.out.println(top.next.value);
        System.out.println(top.next.next.value);
        System.out.println(top.next.next.prev.value);
        System.out.println(top.next.next.prev.prev.value);

        for (int i = 1; i < 42; i++) {
            p.value = i;
            if (i != 41){
                p.next = new Node<>();
                p.next.prev = p;
                p = p.next;
            }
        }
        //收尾相连
        p.next = top;
        top.prev = p;

        //打印验证是否成功创建了双向循环链表
//        p = top;
//        for (int i = 1; i < 42; i++) {
//            System.out.print(p.value+" ");
//            p = p.next;
//        }
//        System.out.println();
//
//        p = top;
//        for (int i = 1; i < 42; i++) {
//            System.out.print(p.value+" ");
//            p = p.prev;
//        }
//        System.out.println();

        //约瑟夫环
        p = top;
        for (int i = 1; ; i++) {
            if (p.next == p){
                //p的下一个是自己, p就是最后一个人, 自己报数123,自己开枪, 游戏结束
                System.out.print(p.value+" ");
                break;
            }
            if (i%3==0){
                //报到3了, 得死
                System.out.print(p.value+" ");
                //这个人得出链表
                p.prev.next = p.next;
                p.next.prev = p.prev;
            }
            p = p.next;
        }
    }





    static class Node<T>{

        T value;

        Node<T> prev;

        Node<T> next;
    }
}
